﻿using System;
using System.Linq;

namespace BackTracking
{
    /* Problem description:
     * A Maze is given as N*N binary matrix of blocks where source block is the upper left most block
     * i.e., maze[0][0] and destination block is lower rightmost block i.e., maze[N-1][N-1].
     * A rat starts from source and has to reach destination. 
     * The rat can move only in two directions: forward and down.
     * 
     * original link: http://www.geeksforgeeks.org/archives/13376
     */

    class AntInMaze
    {
        static int Dimention = 5; // dimention of the maze
 
        /* Algorithm
         * 
         * If destination is reached
         *   print the solution matrix
         * Else
         *   a) Mark current cell in solution matrix as 1.
         *   b) Move forward in horizontal direction and recursively check if this move leads to a solution.
         *   c) If the move chosen in the above step doesn't lead to a solution
         *      then move down and check if  this move leads to a solution.
         *   d) If none of the above solutions work then unmark this cell as 0 
         *      (BACKTRACK) and return false.
         */
 
        //question: in multi-dimentional array, how to get the dimentions and how many elements in each dimention?
 
        /* A utility function to print solution matrix sol[N][N] */
        public void PrintSolution(int[,] maze)
        {
            for (int i = 0; i < Dimention; i++)
            {
                for (int j = 0; j < Dimention; j++)
                    Console.Write(" {0} ", maze[i, j]);
                Console.WriteLine();
            }
        }
 
        /* A utility function to check if x,y is valid index for N*N maze */
        public bool IsSafe(int[,] maze, int x, int y)
        {
            //if (x,y outside maze) return false    
            if( (x >= 0 && x < Dimention) && (y >= 0 && y < Dimention) && (maze[x,y] == 1))
                return true;     

            return false;
        }
 
        /* A recursive utility function to solve Maze problem */
        private bool SolveMazeUtil(int[,] maze, int x, int y, int[,] sol)
        {
            // if (x,y is goal) return true    
            if ((x == Dimention-1) && (y == Dimention-1))
            {
                sol[x,y] = 1;   
                return true;
            }
 
            // Check if maze[x][y] is valid    
            if(IsSafe(maze, x, y) == true)    
            {
                // mark x,y as part of solution path        
                sol[x,y] = 1;

                /* Move forward in x direction */ 
                if (SolveMazeUtil(maze, x+1, y, sol) == true)      
                    return true; 
 
                // If x moving in x direction doesn't give solution 
                // then Move down in y direction  
                if (SolveMazeUtil(maze, x, y+1, sol) == true)     
                    return true;                

                /* If none of the above movements work then BACKTRACK:   
                 * unmark x,y as part of solution path */ 
                sol[x,y] = 0;

                return false;   
            }

            return false;
        }
 
        /* This function solves the Maze problem using Backtracking.  
         * It mainly usessolveMazeUtil() to solve the problem. 
         * It returns false if no path is possible,
         * otherwise return true and prints the path in the form of 1s. 
         * Please note that there may be more than one solutions, 
         * this function prints one of the feasible solutions.*/
        bool solveMaze(int[,] maze)
        {
            int[,] sol = { { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 } };
 
            if (SolveMazeUtil(maze, 0, 0, sol) == false)
            {
                Console.WriteLine("Solution doesn't exist");       
                return false; 
            }

            PrintSolution(sol); 

            return true;
        }
 
        static void Main(string[] args)
        {
            int[,] maze  =  { {1, 0, 0, 0, 1}, {1, 0, 1, 0, 1}, {1, 1, 0, 1, 0}, {0, 1, 1, 1, 1}, {0, 0, 0, 1, 1}    };  
            AntInMaze ant = new AntInMaze();
 
            Console.WriteLine("Maze: ");
            ant.PrintSolution(maze);
 
            Console.WriteLine("Solution: ");
            ant.solveMaze(maze);

            Console.WriteLine("Press any key to finish...");
            Console.ReadKey();
        }
    }
 
}